/*
 * @Author: szx
 * @Date: 2022-03-01 14:24:38
 * @LastEditTime: 2022-03-01 15:04:00
 * @Description:
 * @FilePath: \leetcode\600-699\648\648.js
 */
/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
// var replaceWords = function (dictionary, sentence) {
//     const arr = sentence.split(' ');
//     const set = new Set(dictionary);
//     for (let i = 0; i < arr.length; i++) {
//         for (let j = 1; j <= arr[i].length; j++) {
//             if (set.has(arr[i].substring(0, j))) arr[i] = arr[i].substring(0, j);
//         }
//     }
//     return arr.join(' ');
// };

// class Trie {
//     constructor() {
//         this.dictionary = {};
//     }

//     insert(word) {
//         let node = this.dictionary;

//         for (const c of word) {
//             if (!node[c]) node[c] = { isEnd: false, word: word };
//             node = node[c];
//         }

//         node['isEnd'] = true;
//         node['word'] = word;
//     }

//     search(word) {
//         let node = this.dictionary;

//         for (const c of word) {
//             if (!node[c]) return word;
//             else if (!node[c]['isEnd']) node = node[c];
//             else return node[c]['word'];
//         }

//         return word;
//     }
// }

// const replaceWords = (dictionary, sentence) => {
//     let trie = new Trie();

//     for (const root of dictionary) trie.insert(root);
//     console.log(trie.dictionary);
//     return sentence
//         .split(' ')
//         .map((word) => trie.search(word))
//         .join(' ');
// };

class Trie {
    constructor() {
        this.dictionary = {};
    }

    insert(word) {
        let node = this.dictionary;

        for (const c of word) {
            if (!node[c]) node[c] = {};
            node = node[c];
        }
        node.isEnd = true;
        node.word = word;
    }

    search(word) {
        let node = this.dictionary;
        for (const c of word) {
            if (!node[c]) return word;
            else if (node[c]?.isEnd) return node[c].word;
            else node = node[c];
        }
        return word;
    }
}

const replaceWords = (dictionary, sentence) => {
    let trie = new Trie();

    for (const root of dictionary) trie.insert(root);
    return sentence
        .split(' ')
        .map((word) => trie.search(word))
        .join(' ');
};

const replaceWords = (dictionary, sentence) => {
    const words = sentence.split(" ");
    const search = (word) => {
        for(const root of dictionary){
            if(word.startsWith(root)){
                word = root;
            }
        }
        return word;
    };
    return words.map(word => search(word)).join(" ");
};
console.log(replaceWords(['cat', 'bat', 'rat'], 'the cattle was rattled by the battery'));
console.log(replaceWords(['a', 'b', 'c'], 'aadsfasf absbs bbab cadsfafs'));
